package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @功能职责:
 * 给定两个数组，编写一个函数来计算它们的交集。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2,2]
 * 示例 2:
 *
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[4,9]
 *  
 *
 * 说明：
 *
 * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
 * 我们可以不考虑输出结果的顺序。
 * 进阶：
 *
 * 如果给定的数组已经排好序呢？你将如何优化你的算法？
 * 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
 * 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @描述： 交集
 * @作者: 郭辉
 * @创建时间: 2020-12-02
 * @copyright Copyright (c) 2020 中国软件与技术服务股份有限公司
 * @company 中国软件与技术服务股份有限公司
 */
public class Intersection {

    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> result = new ArrayList<>();

        //将两个数组都转换为list
        List<Integer> nums1List = new ArrayList<>();
        for (int i = 0 ; i < nums1.length; i ++){
            nums1List.add(nums1[i]);
        }

        List<Integer> nums2List = new ArrayList<>();
        for (int i = 0 ; i < nums2.length; i ++){
            nums2List.add(nums2[i]);
        }

        //暴力搜索，num1 中的元素，遍历num2，如果有，则将其放入结果集，并且将该数值为-1
        for (int i = 0 ; i < (nums1List.size()); i++){
            for (int j = 0; j < (nums2List.size()); j++){
               /* System.out.println(nums1List.get(0));
                if (j == 144){
                    System.out.println(nums2List.get(144));
                    System.out.println(nums1List.get(0) .equals(nums2List.get(144)));
                }*/
                if (
                        nums1List.get(i) != -1
                                && nums2List.get(j) != -1
                                && nums1List.get(i) .equals( nums2List.get(j))
                ){
                    result.add(nums1List.get(i));
                    nums1List.set(i,-1);
                    nums2List.set(j,-1);
                    break ;
                }
            }
        }

        int[] res = new int[result.size()];
        for (int i = 0; i < res.length; i++){
            res[i] = result.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        Intersection solution = new Intersection();
       /* int [] pam1 = {1,2,2,3,3,5};
        int [] pam2 = {2,3,2,5};*/
        int [] pam1 = {180,395,311,750,949,164,212,968,978,404,381,1,265,92,331,350,375,451,903,932,129,590,771,883,900,344,712,804,367,547,596,533,22,691,125,558,450,74,771,673,778,45,44,172,63,260,669,374,526,337,138,459,724,458,428,851,536,387,93,586,453,715,29,330,60,648,541,923,244,377,164,780,748,831,708,544,176,985,1,308,256,922,645,121,42,855,667,730,115,677,289,355,478,298,849,218,730,449,621,957,244,25,22,866,287,704,841,757,916,439,124,316,575,642,4,84,345,157,4,578,359,223,936,275,997,197,478,795,369,963,733,252,18,872,690,851,985,49,124,646,153,396,150,499,96,699,848,541,214,201,544,249,974,599,937,583,711,298,375,137,829,913,625,897,757,795,266,298,6,404,809,6,879,20,943,293,717,146,634,835,805,532,75,256,115,994,147,368,784,716,579,127,341,195,233,75,194,858,741,507,932,648,610,239,604,626,67,203,793,769,429,760,466,540,258,977,614,781,276,832,771,538,296,990,832,146,895,42,458,681,582,444,301,72,786,977,483,266,868,693,703,593,536,581,594,448,793,606,71,556,230,652,711,704,8,871,700,681,431,921,655,745,344,285,842,856,401,541,364,117,933,175,250,410,608,805,446,358,233,921,430,743,126,662,22,793,371,452,55,432,521,811,548,556,160,974,567,816,802,357,379,527,237,435,669,381,583,124,188,510,6,144,493,316,135,444,251,653,656,952,49,451,558,181,838,227,605,41,677,738,858,603,888,463,406,765,754,10,956,898,815,123,727,961,816,801,243,102,606,538,581,49,424,388,746,483,682,573,666,391,764,490,879,353,861,768,24,306,499,143,363,775,453,221,85,450,874,842,836,554,518,799,116,27,455,826,995,436,429,851,613,147,42,363,946,505,510,705,192,729,809,715,390,267,364,808,733,878,919,20,877,997,917,590,196,80,868,173,325,249,346,961,734,235,27,374,914,363,905,796,399,153,51,267,522,440,630,344,719,216,787,442,589,897,419,950,777,916,534,584,277,910,372,107,732,409,73,496,927,92,317,500,609,584,806,934,382,864,656,606,165,762,407,461,957,851,795,458,470,340,83,381,323,980,457,204,313,793,949,388,985,432,172,292,184,778,924,613,756,692,874,706,527,232,397,907,28,97,899,573,282,349,104,809,318,286,258,504,908,604,765,676,148,476,283,427,975,967,178,401,593,578,711,981,599,846,362,682,612,683,902,886,648,533,811,527,961,331,602,679,726,13,321,969,78,968,760,824,266,717,303,233,630,306,81,902,896,827,453,137,184,675,835,259,335,945,204,569,237,396,646,629,411,975,291,158,87,240,382,681,756,773,440,235,687,137,748,478,670,808,132,834,24,345,240,505,732,294,794,267,433,273,100,888,634,754,947,691,469,156,873,661,583,380,789,192,37,621,798,347,401,953,395,888,386,876,692,530,784,27,211,772,612,162,209,392,21,352,959,95,784,482,588,924,738,862,463,571,731,47,698,751,569,532,870,118,677,202,208,201,573,672,358,112,501,424,802,851,202,543,620,967,159,977,614,903,797,765,99,667,999,528,220,365,263,610,513,652,781,249,453,256,371,751,492,646,544,673,130,199,987,279,866,739,599,50,197,479,114,153,121,512,828,246,701,23,103,231,426,109,547,530,14,694,37,281,339,351,396,773,406,965,773,748,118};
        int [] pam2 = {867,616,238,748,559,454,139,699,763,776,47,123,14,332,545,680,562,478,593,401,396,75,489,880,142,965,795,544,691,981,711,470,172,965,167,223,690,100,934,402,699,260,944,904,659,412,934,86,733,83,189,631,542,392,424,739,167,342,695,160,648,441,885,631,637,910,528,299,137,342,115,839,62,660,285,578,992,38,287,669,534,469,464,282,788,283,701,122,818,140,330,684,524,994,419,920,191,110,619,389,575,365,916,188,396,454,115,639,784,873,511,337,308,895,313,300,672,277,297,518,545,297,847,6,395,196,791,246,586,331,547,382,443,103,174,942,890,530,590,660,899,651,837,732,180,979,517,47,241,290,571,985,590,613,580,290,549,770,99,922,70,538,24,263,327,445,220,577,584,473,710,893,59,961,189,278,454,515,678,143,46,588,901,55,382,456,337,715,331,155,178,547,491,977,832,193,124,571,896,834,6,655,712,229,954,308,491,820,891,903,839,61,244,0,832,862,15,861,738,189,489,311,888,661,158,65,724,374,431,957,387,80,795,702,798,702,93,761,659,423,984,522,656,449,271,123,499,723,588,216,961,357,57,495,171,656,340,409,6,672,726,302,70,190,833,920,346,133,606,24,316,58,462,153,288,943,688,667,369,400,73,330,214,99,603,320,942,513,641,962,577,922,196,373,164,474,437,851,378,756,336,269,625,737,498,471,522,525,102,966,331,689,877,735,983,168,66,460,884,838,982,687,857,627,80,209,311,567,771,420,126,558,146,297,840,525,655,309,281,271,178,125,510,471,598,298,566,750,105,139,533,16,11,590,131,991,795,439,712,654,902,86,727,580,258,661,116,226,40,529,497,278,351,862,98,24,525,844,168,780,142,798,138,323,515,529,103,939,8,301,144,473,842,970,928,626,242,243,789,734,429,786,309,130,710,921,423,824,658,704,516,343,217,881,116,49,485,956,608,73,584,266,919,181,485,526,498,430,252,970,483,93,623,112,910,431,233,322,993,133,642,482,905,996,558,810,707,94,510,958,639,274,733,421,997,5,736,144,0,228,446,289,453,281,234,0,757,18,38,980,354,288,42,178,904,166,563,736,886,602,422,391,259,383,407,9,381,566,968,827,138,107,411,694,323,815,27,361,656,288,153,914,83,175,731,214,351,996,418,554,560,176,549,20,411,890,64,232,429,48,833,33,366,184,569,568,942,616,328,650,590,354,650,325,498,727,932,505,148,14,696,631,824,472,586,444,796,403,936,889,392,308,829,977,19,753,905,682,947,89,349,284,136,241,616,859,26,711,122,154,685,515,754,308,595,873,206,793,942,100,502,496,595,587,685,935,446,315,91,91,17,251,72,137,712,610,789,59,646,828,946,27,654,707,838,623,950,657,93,761,214,281,582,238,600,796,641,195,678,263,32,580,311,958,231,862,191,421,648,325,29,236,458,539,242,583,748,684,703,291,237,819,588,577,5,540,994,29,823,666,374,151,29,892,322,418,720,828,204,30,935,952,893,709,726,379,978,162,978,87,691,901,269,694,453,121,63,548,264,891,731,497,141,810,263,136,618,651,510,404,608,660,867,342,358,917,906,692,392,811,269,313,925,737,800,997,234,508,294,952,339,49,765,859,512,840,728,981,108,37,37,612,372,423,11,799,458,828,951,29,994,596,945,861,609,871,826,696,71,358,928,294,823,86,140,882,195,522,511,209,488,513,782,272,608,573,607,350,676,792,863,516,565,29,404,510,220,330,97,578,993,302,760,549,754,461,475,644,257,25,664,227,786,468,339,663,580,720,898,633,632,586,857,512,319,666};
        int[] intersect = solution.intersect(pam1, pam2);
        for (int i = 0; i < intersect.length; i++) {
            System.out.println(intersect[i]);
        }
    }

}
